#include<iostream>
#include<vector>
using namespace std;
/*
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
子序列
解题思路：
假设一个dp数组dp[i]表示的含义是以nums[i]结尾的元素的最长递增子序列的长度
所以我们要对nums种的元素进行遍历，如何求以i为结尾的元素的最长递增子序列呢，要找到从0到i-1之间的最长递增子序列的长度
dp[j],如果nums[i]>nums[j],则dp[i]=dp[j]+1,由于我们要求的是0到i的最长递增子序列的最大值，所以有
dp[i] = max(dp[i],dp[j]+1)
*/
int dp(vector<int> nums)
{
    //创建dp数组
    vector<int> dp(nums.size(),1);
    //初始化
    dp[0] = 1;
    int result = 1;
    for(int i=1;i<nums.size();i++)
    {
        for(int j=0;j<i;j++)
        {
            if(nums[i]>nums[j])
            dp[i] = max(dp[i],dp[j]+1);
        }
        if(dp[i]>result)
            result = dp[i];
    }
    return result;
}
int main()
{
    cout<<"enter a number:"<<endl;
    int number;
    cin>>number;
    vector<int> nums(number);
    cout<<"enter nums:"<<endl;
    for(int i=0;i<number;i++)
        cin>>nums[i];
    cout<<dp(nums);
    return 0;
}